#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;
typedef struct node *link;

struct node {
    Item item;
    link next;
};

/**
* Program 3.11 List insertion sort
* --------------------------------------
* This code generates N random integers between 0 and 999,
* builds a linked list with one number per node (first for loop), and
* then rearranges the nodes so that the numbers appear in order when we traverse the list (second for loop).
* 
* To accomplish the sort, we maintain two lists, an input (unsorted) list and an output (sorted) list.
* On each iteration of the loop, we remove a node from the input and insert it into position in the output.
* The code is simplified by the use of head nodes for each list, that contain the links to the first nodes on the lists.
* For example, without the head node, the case where the node to be inserted into the output list goes at the beginning
* would involve extra code.
 */
int main(int argc, char ** argv){
    int N = 10;
    int i;
    struct node heada;
    struct node headb;
    link t = NULL;
    link u = NULL;
    link a = &heada;
    link b = NULL;
    link x = NULL;


    for (i = 0, t = a; i < N; i++) {
        Item item = rand() % 1000;
        t->next = malloc(sizeof(*t));
        t = t->next;
        t->item = item;
        t->next = NULL;
    }

    link curr = a->next;
    while (curr != NULL) {
        printf("%d ", curr->item);
        curr = curr->next;
    }
    printf("\n");

    b = &headb;
    b->next = NULL;

    for (t = a->next; t != NULL; t = u) {
        u = t->next;
        for (x = b; x->next != NULL; x = x->next) {
            if (x->next->item > t->item) {
                break;
            }
        }
        t->next = x->next;
        x->next = t;
    }

    link currb = b->next;
    while (currb != NULL) {
        printf("%d ", currb->item);
        currb = currb->next;
    }
    printf("\n");

    return 0;
}